package 树.AVL树;

import java.util.NoSuchElementException;

public class AVL {
    class AVLNode{
        AVLNode left;
        AVLNode right;

        int val;
        int height;

        public AVLNode(int val) {
            this.val = val;
        }

        public AVLNode(AVLNode left, AVLNode right, int val) {
            this.left = left;
            this.right = right;
            this.val = val;
        }
    }
    AVLNode root;//根节点

    //查询，本质还是二叉搜索树所以和BST是一样的
    public boolean contains(int val){
        return contains(root , val);
    }
    private boolean contains(AVLNode root , int val){
        if (root == null){
            return false;
        }
        if (root.val > val){
            return contains(root.left , val);
        }else if (root.val < val){
            return contains(root.right , val);
        }else {
            return true;
        }
    }
    //求高度,是不是有疑问，节点已经带了高度了，为什么还要专门设立一个方法？后续会有介绍
    private int getHeight(AVLNode root){
        if (root != null)
            return root.height;
        return 0;
    }
    public int getHeight(){
        return getHeight(root);
    }
    //右单旋（LL状态对应的旋转操作）
    private AVLNode llRotating(AVLNode root){
        //这三个步骤完成交换
        AVLNode newRoot = root.left;
        root.left = newRoot.right;
        newRoot.right = root;
        //这两个步骤完成高度更新
        //这里求高度，如果节点是空。。。理解了为啥专门用一个方法求了吧
        root.height = Math.max(getHeight(root.left) , getHeight(root.right)) + 1;
        newRoot.height = Math.max(getHeight(newRoot.left) , getHeight(root)) + 1;
        return newRoot;
    }
    //左单旋（RR状态对应的旋转操作）
    private AVLNode rrRotating(AVLNode root){
        //这三个步骤完成交换
        AVLNode newRoot = root.right;
        root.right = newRoot.left;
        newRoot.left = root;
        //这俩步骤完成高度更新
        root.height = Math.max(getHeight(root.left) , getHeight(root.right)) + 1;
        newRoot.height = Math.max(getHeight(root) , getHeight(newRoot.right)) + 1;
        return newRoot;
    }
    //LR旋转（LR状态旋转）
    private AVLNode lrRotating(AVLNode root){
        //其中ll与rr方法上面有介绍
        root.left = rrRotating(root.left);
        return llRotating(root);
    }
    //RL旋转（RL状态旋转）
    private AVLNode rlRotating(AVLNode root){
        root.right = llRotating(root.right);
        return rrRotating(root);
    }
    public void insert(int val){
        root = insert(root , val);
    }

    private AVLNode insert(AVLNode root, int val) {
        if (root == null){
            root = new AVLNode(null , null , val);
        }else {
            if (root.val > val){
                root.left = insert(root.left , val);
                //看这里，是不是疑问为什么不能是-2：解：如果值比节点val小肯定插在左面那么造成不平衡的位置一定发生在左子树
                if (getHeight(root.left) - getHeight(root.right) == 2){
                    if (root.left.val > val){
                        root = llRotating(root);
                    }else {
                        root = lrRotating(root);
                    }
                }

            }else if (root.val < val){
                root.right = insert(root.right , val);
                if (getHeight(root.right) - getHeight(root.left) == 2){
                    if (root.right.val < val){
                        root = rrRotating(root);
                    }else {
                        root = rlRotating(root);
                    }
                }
            }else {
                //此时节点值与插入值相等
                //可以抛异常throw new NoSuchElementException("老哥哥这个值有了");
                System.out.println("这个值有了");
            }
        }
        root.height = Math.max(getHeight(root.left) , getHeight(root.right)) + 1;
        return root;
    }
    public void delete(int val){
        if (contains(val)){
            root = delete(root , val);
        }else {
            System.out.println("待删除的这个值不存在哦～");
        }
    }
    private AVLNode delete(AVLNode root , int val){
        if (root == null){
            System.out.println("树是空的，没地方删");
            return null;
        }
        if (val < root.val){
            root.left = delete(root.left , val);
            //与插入一样，完成删除操作后，来维持AV，既然删了左子树，那么右面高度肯定是更高的
            if (getHeight(root.right) - getHeight(root.left) == 2){
                if (getHeight(root.right.right) > getHeight(root.right.left)){
                    //相对当前树根是RR状，具体画图在同目录md中有详细解释
                    root = rrRotating(root);
                }else {
                    //此时在RL状态
                    root = rlRotating(root);
                }
            }
        }else if (val > root.val){
            root.right = delete(root.right , val);
            if (getHeight(root.left) - getHeight(root.right) == 2){
                if (getHeight(root.left.left) > getHeight(root.left.right)){
                    root = llRotating(root);
                }else {
                    root = lrRotating(root);
                }
            }
        }else {
            if (root.left != null && root.right != null){
                if (getHeight(root.left) > getHeight(root.right)){
                    int lMax = max(root.left).val;
                    root.val = lMax;
                    delete(root.left , lMax);
                }else {
                    int rMin = min(root.right).val;
                    root.val = rMin;
                    delete(root.right , rMin);
                }
            }else {
                root = root.left == null ? root.right : root.left;
            }
        }
        root.height = Math.max(getHeight(root.left) , getHeight(root.right)) + 1;
        return root;
    }
    private AVLNode min(AVLNode root){
        if (root.left == null){
            return root;
        }
        return min(root.left);
    }
    private AVLNode max(AVLNode root){
        if (root.right == null){
            return root;
        }
        return max(root.right);
    }

}
